package leetcode.code1856;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution extends Solution1856 {

	private final int mod = (int) 1e9 + 7;

	@Override
	public int maxSumMinProduct(int[] nums) {
		int len = nums.length;
//		if (len == 1)// 抖机灵用的
//			return nums[0] * nums[0]; 这是错的 ,需要mod
		long[] sum = new long[len + 1];// 预处理, 为了后续求[i..j]范围累加和
		sum[0] = 0;
		for (int i = 1; i <= len; i++) {
			sum[i] = sum[i - 1] + nums[i - 1];
		}
		Stack<List<Integer>> s = new Stack<>();// 可处理重复的单调栈
		long ans = 0;
		for (int i = 0; i < len; i++) {
			while (!s.isEmpty() && nums[s.peek().get(0)] > nums[i]) {// 强迫营业 , 弹弹弹
				List<Integer> maxList = s.pop();
				int left = s.isEmpty() ? 0 : s.peek().get(s.peek().size() - 1) + 1;
				int num = nums[maxList.get(0)];// 栈顶数字
				ans = Math.max(ans, (sum[i] - sum[left]) * num);// 结算答案
			}
			if (!s.isEmpty() && nums[s.peek().get(0)] == nums[i]) {// 相同数字进栈
				s.peek().add(i);
			} else {// 新数字进栈
				List<Integer> list = new ArrayList<>();
				list.add(i);
				s.add(list);
			}
		}
		while (!s.isEmpty()) {// 结算栈内剩余数字
			List<Integer> maxList = s.pop();
			int left = s.isEmpty() ? 0 : s.peek().get(s.peek().size() - 1) + 1;
			int num = nums[maxList.get(0)];// 栈顶数字
			ans = Math.max(ans, (sum[len] - sum[left]) * num);
		}
		return (int) (ans % mod);
	}

	private long sum(int[] nums, int i, int j) {
		long ans = 0;
		for (; i < j; i++) {
			ans += nums[i];
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();

	}

}
